786.第 K 个最小的素数分数

1、题干

给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干素数组成，且其中所有整数互不相同。

对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。

那么第 k 个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。

示例 1：

输入：arr = [1,2,3,5], k = 3
输出：[2,5]
解释：已构造好的分数,排序后如下所示: 
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5

示例 2：

输入：arr = [1,7], k = 1
输出：[1,7]

提示：

2 <= arr.length <= 1000
1 <= arr[i] <= 3 * 10⁴
arr[0] == 1
arr[i] 是一个素数，i > 0
arr 中的所有数字 互不相同 ，且按 严格递增 排序
1 <= k <= arr.length * (arr.length - 1) / 2

进阶：你可以设计并实现时间复杂度小于 O(n²) 的算法解决此问题吗？

2、解法1-暴力解法

创建数组matrix，两层循环遍历素数数组，把所有素数对存入matrix中，然后对matrix进行排序。最先尝试了暴力解法，居然过了。。。

3、代码

var kthSmallestPrimeFraction = function (arr, k) {
    const p = [];
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            p.push([arr[j], arr[i]]);
        }
    }

    p.sort((a, b) => a[0] / a[1] - b[0] / b[1]);

    return p[k - 1];
};

时间复杂度: $O(n^2*log(n^2))$
执行用时: 1908 ms，内存消耗: 94 MB

4、解法2-暴力解法的二分优化

之后尝试使用二分法优化这段代码，这里二分的目标是matrix而不是原始数组arr，因为时间复杂度最高的地方在matrix的排序。优化后时间复杂度量级没有改变，但是matrix长度减半，执行速度会有所提升

思路是：

创建两个数组m1和m2，两层循环遍历素数数组
把所有商小于0.5的素数对存入m1中，其余存入m2中
如果k <= m1.length就对m1排序并返回m1[k-1]
如果k > m1.length就对m2排序并返回m2[k - m1.length - 1]

5、代码

var kthSmallestPrimeFraction = function (arr, k) {
    const p1 = [];
    const p2 = [];
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[j] / arr[i] < 0.5) {
                p1.push([arr[j], arr[i]]);
            } else {
                p2.push([arr[j], arr[i]]);
            }
        }
    }

    if (k <= p1.length) {
        p1.sort((a, b) => a[0] / a[1] - b[0] / b[1]);
        return p1[k - 1];
    } else {
        p2.sort((a, b) => a[0] / a[1] - b[0] / b[1]);
        return p2[k - p1.length - 1];
    }
};

时间复杂度: $O(n^2*log(n^2))$
执行用时: 1276 ms 内存消耗: 104.1 MB

6、解法3-桶排序

二分方案中，把matrix二分后两个子数组的元素个数的数量级几乎相当，其实推广到 $N(2<N<=n*(n-1)/2,n=1000)$ 也适用。也就是说matrix分成N个子组后每个子组的长度几乎相等，这其实就是桶排序。

所以如果这样理解题意就简单很多：数组中最多包含约500000（ $n*(n-1)/2,n=1000$ ）个无序排列的小数，这些小数从0到1均匀分布，返回其中第k小的小数。

桶排序的思路：

创建大小为N的二维数组matrix，matrix中的每个元素(数组)就是一个桶
根据分组规则把所有小数均匀放入桶中
累计每个桶内元素数量，找到第k个小数所在的桶matrix[k']，对该桶内小数进行排序
在matrix[k']这个桶中找到第k个小数即可

小数的分组规则：

分组的关键问题是分组规则，也就是任意小数a应该放入桶的序号i是多少（即a与i之间的映射关系）
实际上可以用桶的数量 $N$ 乘以小数 $a$ 再取整作为桶的序号，即 $i=Math.trunc(a*N)$ ，这样就建立起小数a与桶序号i的映射，消耗的时间复杂度是 $O(1)$

对于这个分组规则可以举个例子：假设 $N$ 取 $1000$ ，对于任意小数 $0.0012$ ，把数据代入公式 $i=Math.trunc(a*N)$ 中算得 $i=1$ ，也就是说 $0.0012$ 应该放入 $matrix[1]$ 这个桶中。

还是在暴力解法的基础上优化，只需要把matrix分为N个子数组，然后只对包含第k个小数的子数组进行排序，最后返回对应的素数对即可。

如果N的取值合适的话，时间复杂度可以降到 $O(n^2)$ 。这里使用的取值计算公式是：N = 10 ** Math.trunc(Math.log10(arr[arr.length - 1]))。

7、代码

var kthSmallestPrimeFraction = function (arr, k) {
    const BASE = 10 ** Math.trunc(Math.log10(arr[arr.length - 1]));
    const matrix = new Array(BASE);
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            const index = Math.trunc(arr[j] / arr[i] * BASE);
            if (!matrix[index]) matrix[index] = [];
            matrix[index].push([arr[j], arr[i]]);
        }
    }

    for (let arr of matrix) {
        arr = arr || [];
        if (k - arr.length <= 0) {
            arr.sort((a, b) => a[0] / a[1] - b[0] / b[1]);
            return arr[k - 1];
        }
        k = k - arr.length;
    }
};

时间复杂度: $O(n^2)$
执行用时: 876 ms 内存消耗: 97.8 MB

8、解法4-桶排序优化

每个桶都使用Array.push放入数据，最终只使用了其中一个桶进行排序，这在时间和空间上都存在大量浪费。可以进一步优化为，只在包含第k个小数的桶中存入素数对，其他的桶只记录元素个数即可。

程序最终逻辑：

计算分组数量N
初始化matrix并写入N个0
双层遍历arr，计算每个桶包含小数的数量
按桶累计小数数量，找到第k个小数对应的桶序号index，将桶matrix[index]赋值为空数组
双层遍历arr，当小数对应的序号与index相等时，将素数对放入桶matrix[index]中
对桶matrix[index]进行排序，返回第k个素数对

9、代码

var kthSmallestPrimeFraction = function(arr, k) {
  // 计算分组数量N
  const N = 10 ** Math.trunc(Math.log10(arr[arr.length - 1]));
  // 初始化matrix并写入N个0
  const matrix = new Array(N).fill(0);

  // 双层遍历arr，计算每个桶包含小数的数量
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      const m = Math.trunc((arr[j] / arr[i]) * N);
      matrix[m] += 1;
    }
  }

  // 按桶累计小数数量，找到第k个小数对应的桶序号index，将桶`matrix[index]`赋值为空数组
  let index = 0;
  for (let i = 0; i < matrix.length; i++) {
    if (k - matrix[i] <= 0) {
      index = i;
      matrix[index] = [];
      break;
    }
    k = k - matrix[i];
  }

  // 双层遍历arr，当小数对应的序号与index相等时，将素数对放入桶`matrix[index]`中
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      const m = Math.trunc((arr[j] / arr[i]) * N);
      if (index === m) matrix[m].push([arr[j], arr[i]]);
    }
  }

  // 对桶`matrix[index]`进行排序，返回第k个素数对
  matrix[index].sort((a, b) => a[0] / a[1] - b[0] / b[1]);
  return matrix[index][k - 1];
};

时间复杂度: $O(n^2)$
执行用时: 92 ms 内存消耗: 41.1 MB

1、题干​

2、解法1-暴力解法​

3、代码​

4、解法2-暴力解法的二分优化​

5、代码​

6、解法3-桶排序​

7、代码​

8、解法4-桶排序优化​

9、代码​